package com.lz.learning;

import com.lz.common.ArrayUtils;

public class FloodFill {
    public static void main(String[] args) {

        FloodFill floodFill = new FloodFill();
        int[][] array = new int[][]{{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};
        floodFill.floodFill(array, 1, 1, 2);


        System.out.println(ArrayUtils.toString2(array));

    }

    /**
     * 面试题 08.10. 颜色填充
     * <p>
     * 输入：
     * image = [[1,1,1],[1,1,0],[1,0,1]]
     * sr = 1, sc = 1, newColor = 2
     * 输出：[[2,2,2],[2,2,0],[2,0,1]]
     * 解释:
     * 在图像的正中间，(坐标(sr,sc)=(1,1)),
     * 在路径上所有符合条件的像素点的颜色都被更改成2。
     * 注意，右下角的像素没有更改为2，
     * 因为它不是在上下左右四个方向上与初始点相连的像素点。
     */


    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int originColor = image[sr][sc];

        floodFill(image, sr, sc, originColor, newColor);
        return image;

    }

    /**
     * 核心问题判断其上下左右,有缺陷 如果颜色相同 则会死递归
     * <p>
     * 重复问题
     *
     * @param image
     * @param sr
     * @param sc
     * @param originColor
     * @param newColor
     */
    private void floodFill(int[][] image, int sr, int sc, int originColor, int newColor) {

        // 边界判断
        boolean bound = sr < 0 || sr >= image.length || sc < 0 || sc >= image[0].length;
        if (bound) return;
        if (image[sr][sc] != originColor) return;
        image[sr][sc] = newColor;

        floodFill(image, sr, sc + 1, originColor, newColor);
        floodFill(image, sr, sc - 1, originColor, newColor);
        floodFill(image, sr + 1, sc, originColor, newColor);
        floodFill(image, sr - 1, sc, originColor, newColor);

    }

    /**
     * 解决重复问题，类似回溯
     *
     * @param image
     * @param sr
     * @param sc
     * @param originColor
     * @param newColor    （0-2^31-1）
     */
    private void floodFill02(int[][] image, int sr, int sc, int originColor, int newColor) {


        // 边界判断
        boolean bound = sr < 0 || sr >= image.length || sc < 0 || sc >= image[0].length;
        if (bound) return;
        if (image[sr][sc] != originColor) return;
        // 先将其置为 -1
        image[sr][sc] = -1;

        floodFill(image, sr, sc + 1, originColor, newColor);
        floodFill(image, sr, sc - 1, originColor, newColor);
        floodFill(image, sr + 1, sc, originColor, newColor);
        floodFill(image, sr - 1, sc, originColor, newColor);
        // 更改
        image[sr][sc] = newColor;
    }

    /**
     * 自动魔棒工具   (扫雷)
     * <p>
     * 1、颜色不一定是一个定值，在一定范围
     * 2、标出边界即可，边界条件
     */

    boolean[][] actived = new boolean[256][256];
    int threshold = 1;

    public int magic(int[][] image, int sr, int sc, int originColor, int newColor) {

        // 边界判断
        boolean bound = sr < 0 || sr >= image.length || sc < 0 || sc >= image[0].length;
        if (bound) return 0;

        // 颜色一定范围内满足
        if (Math.abs(image[sr][sc] - originColor) > threshold)
            return 0;
        // if (image[sr][sc] != originColor) return 0;
        // 只要访问过1
        if (actived[sc][sc]) return 1;
        actived[sc][sr] = true;
        // 上下左右都有
        int n = magic(image, sr, sc + 1, originColor, newColor) +
                magic(image, sr, sc - 1, originColor, newColor) +
                magic(image, sr + 1, sc, originColor, newColor) +
                magic(image, sr - 1, sc, originColor, newColor);
        // 更改
        if (n < 4)
            image[sr][sc] = newColor;

        return 1;
    }
}
